j) (40 bodov)

Najdôležitejšia úloha, ktorou ťa poverili, je získať informácie o Z-civilizácii a zanalyzovať ich. Z-civilizácia dala vesmíru napríklad zeleninu a preto je v našom záujme preskúmať ju. Jednou z hlavných informácii je počet obyvateľov Z-planéty. Z-planéta má väčšinu povrchu pokrytú zhubným zinkom a preto je obývaná len jej veľmi malá časť. Na nej sa neprejavuje zakrivenie planéty, preto si ju predstavíme ako rovinu. Táto časť má obdĺžnikový tvar a je rozdelená na RxC štvorcových parciel. Na každej parcele môže byť postavený najviac jeden z-dom (tzv. zrub). Z-ľudia majú ale zmysel pre pravidelnosť a preto si domy nestavajú len tak kade-tade, ale do takéhoto pravidelného útvaru (4x4 parcely, mriežka znamená zastavanú parcelu, bodka prázdnu):

####
..#.
.#..
####

Tento útvar sa ale pravidelne opakuje aj vo väčšej mierke: oblasť parciel 16x16 pozostáva z 4x4 menších oblastí, na ktorých sa podľa z-útvaru vyskytujú úplne prázdne oblasti, alebo menšie pravidelne zastavané oblasti:

################
..#...#...#...#.
.#...#...#...#..
################
........####....
..........#.....
.........#......
........####....
....####........
......#.........
.....#..........
....####........
################
..#...#...#...#.
.#...#...#...#..
################

Oblasť 64x64 vyzerá úplne rovnako, ak každú bodku nahradíme úsekom bodiek 4x4 a každú mriežku úsekom 4x4 zastavanou podľa z-útvaru a takto sa dá postupovať až k ľubovoľne veľkým rozmerom (potenciálne až do nekonečna). Našou úlohou je zistiť počet domov na nejakej podoblasti z-planéty. Napíšte program, ktorý načíta z jediného riadku vstupu 4 medzerami oddelené čísla: dva protiľahlé rohy obdĺžnika R1,C1,R2,C2 (1<= R1,C1,R2,C2 <= 262144) a na jediný riadok výstupu vypíše jediné číslo: počet domov v tomto obdĺžniku. Môžete predpokladať, že táto odpoveď nepresahuje 10^9. Ľavý horný roh má súradnicu 1,1, smerom dole sa zvyšuje prvá súradnica, smerom doprava druhá súradnica. Zaujímajú nás hodnoty vrátane.

Príklad:

Vstup:

1 1 10 8

Výstup:

25

Vstup:

5 9 3 1

Výstup:

12

Vstup:

4 17 34521 65410

Výstup:

51690453

---